#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int T,n;
const int MAXN=2e5+5;
int A[MAXN],B[MAXN];
int stat[MAXN];
ll ans;
/*
inline int bit(int num,int n){
    return (num>>(n-1))&1;
}

inline void solve(int n){
    for(int i=0;i<=(1<<(n-1))){
        for(int j=n;j>=1;--j)
    }
}*/

inline void check_and_do(int st,int ed){
    int flag=2;
    int flag2=0;
    for(int i=st+1;i<=ed-1;++i){
        if(stat[i]==0) continue;
        flag2=1;
        if(flag==2) flag=stat[i];
        if(flag!=2 && stat[i]!=flag){
            flag=2;
            break;
        }
    }
    if(flag2==0){
        stat[st]=1;
        stat[ed]=1;
        ans+=A[st];
        return;
    }
    if(flag!=2){
        for(int i=st+1;i<=st-1;++i){
            stat[i]=flag;
        }
        stat[st]=-1*flag;
        stat[ed]=-1*flag;
        ans+=A[st];
    }
}

inline void solve(int n){
    int cnt=1;
    for(int i=1;i<=n;++i){
        if(B[i]){
            B[cnt++]=i;
        }
    }

    while(--cnt){
        int st=0;
        for(int i=1;i<=n;++i){
            if(A[i]==B[cnt] && st != 0){
                check_and_do(st,i);
                st=0;
            }
            else if(A[i]==B[cnt]) st=i;

        }
    }
}

signed main(){

    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    cin>>T;
    for(int i=1;i<=T;++i){
        cin>>n;
        for(int j=1;j<=n;++j){
            cin>>A[j];
            B[A[j]]=1;
        }
        //reverse(A+1,A+n+1)
        solve(n);
        cout<<ans<<"\n";
        memset(B,0,sizeof(B));
        memset(stat,0,sizeof(stat));
        ans=0;
    }

    return 0;
}
